package graph.algo;

import graph.model.Graph;

/**
 * The All Pairs Shortest Path problem - find shortest distances between every
 * pair of vertices in a given edge weighted directed Graph.
 *
 * <p>
 * Floyd's Algorithm to for All Pairs Shortest Path problem :
 * </p>
 * The idea is to one by one pick all vertices and update all shortest paths
 * which include the picked vertex as an intermediate vertex in the shortest
 * path. When we pick vertex number k as an intermediate vertex, we already have
 * considered vertices {0, 1, 2, .. k-1} as intermediate vertices. For every
 * pair (i, j) of source and destination vertices respectively, there are two
 * possible cases.
 * <ol>
 * <li>k is not an intermediate vertex in shortest path from i to j. We keep the
 * value of dist[i][j] as it is.</li>
 * <li>k is an intermediate vertex in shortest path from i to j. We update the
 * value of dist[i][j] as dist[i][k] + dist[k][j].</li>
 *
 * @author shankark
 * @link http://www.geeksforgeeks.org/dynamic-programming-set-16-floyd-warshall-
 *       algorithm/
 */
public class AllPairShortestPath {
	Graph graph;
	int v;
	int[][] adjMatrix;
	static final int INFINITY = 99999;

	public AllPairShortestPath(Graph graph) {
		this.graph = graph;

		v = graph.getVertices().length;
		adjMatrix = new int[v][v];

		// copy the adjacency matrix of the graph
		int[][] gAdjMatrix = graph.getAdjMatrix();
		for (int i = 0; i < v; i++) {
			for (int j = 0; j < v; j++) {
				if (gAdjMatrix[i][j] == 0) {
					adjMatrix[i][j] = INFINITY;
				} else {
					adjMatrix[i][j] = gAdjMatrix[i][j];
				}
			}
		}
	}

	public void findAllPairsShortestPath() {
		for (int r = 0; r < v; r++) {
			for (int c = 0; c < v; c++) {
				if (adjMatrix[r][c] != INFINITY) {
					for (int i = 0; i < v; i++) {
						if (adjMatrix[i][r] < INFINITY) {
							if (adjMatrix[i][c] > (adjMatrix[r][c] + adjMatrix[i][r])) {
								adjMatrix[i][c] = adjMatrix[r][c]
										+ adjMatrix[i][r];
							}
						}
					}
				}
			}
		}

		// display the shortest paths
		System.out.println("All pairs shortest path:");
		for (int i = 0; i < v; i++) {
			for (int j = 0; j < v; j++) {
				System.out.print(adjMatrix[i][j] + " ");
			}
			System.out.println();
		}
	}

	public static void main(String[] args) {
		Graph graph = new Graph(4, 6, true, true);

		graph.addVertex(0, 'a');
		graph.addVertex(1, 'b');
		graph.addVertex(2, 'c');
		graph.addVertex(3, 'd');

		graph.addEdge(0, 3, 10);
		graph.addEdge(0, 1, 5);
		graph.addEdge(1, 2, 3);
		graph.addEdge(2, 3, 1);

		AllPairShortestPath shortestPath = new AllPairShortestPath(graph);
		shortestPath.findAllPairsShortestPath();
	}
}
